'''
https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/description/
'''
from collections import deque
from typing import List

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        distance = [[float('inf')] * n for _ in range(m)]
        distance[0][0] = 0
        q.append((0, 0))
        while q:
            x, y = q.popleft()
            for tx, ty in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if 0 <= tx < m and 0 <= ty < n and distance[x][y] + grid[tx][ty] < distance[tx][ty]:
                    distance[tx][ty] = distance[x][y] + grid[tx][ty]
                    if grid[tx][ty] == 0:
                        q.appendleft((tx, ty))
                    else:
                        q.append((tx, ty))
        return distance[m - 1][n - 1]